package leetcode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 描述:114. 二叉树展开为链表
 *
 * @author Madison You
 * @created 22:39
 */
public class Mid_114_Flatten {
    public static void main(String[] args) {
        TreeNode[] treeNodes = new TreeNode[10];
        for (int i = 0; i < 10; i++) {
            treeNodes[i] = new TreeNode(i + 1);
        }
        for (int i = 0; i < 10; i++) {
            if (i * 2 + 1 < 10) {
                treeNodes[i].left = treeNodes[i * 2 + 1];
            }
            if (i * 2 + 2< 10) {
                treeNodes[i].right = treeNodes[i * 2 + 2];
            }
        }
        flatten(treeNodes[0]);
    }

    public static void flatten(TreeNode root) {
        List<TreeNode> list = new ArrayList<TreeNode>();
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                list.add(node);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        int size = list.size();
        for (int i = 1; i < size; i++) {
            TreeNode prev = list.get(i - 1), curr = list.get(i);
            prev.left = null;
            prev.right = curr;
        }
    }


}
